import java.util.*;
public class Solution {
    //1.旋转图像
    public void rotate(int[][] matrix) {
        //先沿着对角线(左上——右下)进行反转
        //再左右镜面反转
        int len = matrix.length;
        for(int i = 0; i < len; i++){
            for(int j = 0; j < i; j++){
                //画个图，标上下标，自然清晰
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        //左右镜面反转
        int left = 0;
        int right = len - 1;
        while(left < right){
            for(int i = 0; i < len; i++){
                int tmp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = tmp;
            }
            left++;
            right--;
        }
    }
    //2.子集
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        ret.add(new ArrayList<>());//将空集加上
        //遍历数组
        for(int i = 0; i < nums.length; i++){
            //每次添加size个子集
            int size = ret.size();
            for(int j = 0; j < size; j++){
                List<Integer> tmp = new ArrayList<>(ret.get(j));
                tmp.add(nums[i]);
                ret.add(tmp);
            }
        }
        return ret;
    }
    //3.有序数组的平方(暴力)
/*    public int[] sortedSquares(int[] nums) {
        //给每个数平方
        for(int i = 0; i < nums.length; i++){
            nums[i] = (int)Math.pow(nums[i], 2);
        }
        //排序
        Arrays.sort(nums);
        return nums;
    }*/
    //有序数组的平方(双指针)
    public int[] sortedSquares(int[] nums) {
        //把握住一点，平方后的最大值一定在数组的最左边或者最右边
        int len = nums.length;
        //左指针，指向数组最左边
        int left = 0;
        //右指针，指向数组最右边
        int right = len - 1;
        //返回数组
        int[] ret = new int[len];
        //返回数组的下标,从后向前,因为找到的都是最大值
        int index = len - 1;
        while(left <= right){
            //左右边界，谁大，谁就放入
            if(nums[left] * nums[left] > nums[right] * nums[right]){
                ret[index--] = nums[left] * nums[left++];
            }else{
                ret[index--] = nums[right] * nums[right--];
            }
        }
        return ret;
    }
    //4.合并区间
    public int[][] merge(int[][] intervals) {
        //高度
        int high = intervals.length;
        //重写排序，按照每个一维数组的的第一个元素升序排序
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] array1, int[] array2){
                return array1[0] - array2[0];
            }
        });
        int[][] ret = new int[high][2];
        //ret数组的下标
        int index = -1;//从-1开始的原因是，第一次是肯定要放入的，作为下一个数组的上一个数组参考
        //合并数组
        for(int[] interval : intervals){
            //若当前数组的start元素大于上一个数组的end元素
            //则不用合并，直接放入ret
            if(index == -1 || interval[0] > ret[index][1]){
                ret[++index] = interval;
            }else{//否则就要合并数组(选择当前数组和上一个数组的end最大值进行合并)
                ret[index][1] = Math.max(ret[index][1], interval[1]);
            }
        }
        return Arrays.copyOf(ret, index + 1);
    }
    //5.数组中的第K个最大元素(排序法)
/*    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }*/
    //5.数组中的第K个最大元素(堆排序)
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o1 - o2;
            }
        });
        for(int i = 0; i < nums.length; i++){
            if(priorityQueue.size() < k){
                priorityQueue.add(nums[i]);
            }else if(priorityQueue.peek() < nums[i]){
                priorityQueue.poll();
                priorityQueue.add(nums[i]);
            }
        }
        return priorityQueue.peek();
    }
    //6.剑指 Offer 40. 最小的k个数(嗯...)
/*    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        return Arrays.copyOf(arr, k);
    }*/
    //6.剑指 Offer 40. 最小的k个数
    public int[] getLeastNumbers(int[] arr, int k) {
        //先快排
        quickSort(arr);
        return Arrays.copyOf(arr, k);
    }
    public int fundPoint(int[] array, int start, int end){
        int key = array[start];
        while(start < end){
            while(start < end && array[end] >= key){
                end--;
            }
            array[start] = array[end];
            while(start < end && array[start] <= key){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = key;
        return start;
    }
    //三数取中
    private int fundMid(int[] array, int left, int right){
        int mid = (left + right) / 2;
        if(array[left] > array[right]){
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else{
                return mid;
            }
        }
    }
    private void quick(int[] array, int left, int right){
        if(left > right){
            return;
        }
        //三数取中优化
        int mid = fundMid(array, left, right);
        //偷偷换掉第一个元素
        swap(array, left, mid);
        //找基准
        int point = fundPoint(array, left, right);
        quick(array, left, point - 1);
        quick(array, point + 1, right);
    }
    public void quickSort(int[] array){
        quick(array, 0, array.length - 1);
    }
    private void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //7.两个数组的交集(哈希法)
    public int[] intersection(int[] nums1, int[] nums2) {
        //数组大小任意定
        int[] ret = new int[nums1.length];
        //数组下标
        int cur = 0;
        //哈希法
        Set<Integer> set = new HashSet<>();
        Set<Integer> retSet = new HashSet<>();
        //先任意入一个序列
        for(int i = 0; i < nums1.length; i++){
            set.add(nums1[i]);
        }
        //放入
        for(int i = 0; i < nums2.length; i++){
            if(set.contains(nums2[i])){
                retSet.add(nums2[i]);
            }
        }
        //拿出
        for(int i : retSet){
            ret[cur++] = i;
        }
        return Arrays.copyOf(ret, cur);
    }
    //8.指 Offer 53 - I. 在排序数组中查找数字 I(二分搜索进化版)
    public int search(int[] nums, int target) {
        //二分法
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                //找到了,继续找,此时就可以从left开始找起到right
                int count = 0;//计数器
                while(left <= right){
                    if(nums[left] == target){
                        count++;
                    }
                    left++;
                }
                return count;
            }
        }
        return 0;
    }
    //9.剑指 Offer 11. 旋转数组的最小数字
    public int minArray(int[] nums) {
        /**清楚一个道理，如果中间元素大于最左边元素
         *则左边有序，若中间元素小于最右边元素，则右边有序
         */
        int left = 0;
        int right = nums.length - 1;
        //此二分用来找最右边的顺序区间
        while(left < right){
            int mid = (left + right) / 2;
            //右边一定有序，右边就不用看了
            if(nums[mid] < nums[right]){
                right = mid;//这里不-1，是因为有可能当前数字即为所求
            }else if(nums[mid] > nums[right]){//右边一定无序，那就继续往右边靠，找有序的
                left = mid + 1;
            }else{//这里右边不一定有序3,3,1,3,通过缩小右边界即可
                right--;
            }
        }
        return nums[left];
    }
    //10.剑指 Offer 21. 调整数组顺序使奇数位于偶数前面(数组法)
    public int[] exchange(int[] nums) {
        //边界双指针
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        int[] ret = new int[len];
        for(int i = 0; i < len; i++){
            if(nums[i] % 2 != 0){
                ret[left++] = nums[i];
            }else{
                ret[right--] = nums[i];
            }
        }
        return ret;
    }
    //10.剑指 Offer 21. 调整数组顺序使奇数位于偶数前面(双指针)
    public int[] exchange(int[] nums) {
        //边界双指针(原数组操作)
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            //先从左边找到是偶数的
            while(left < right && nums[left] % 2 != 0){
                left++;
            }
            //从右边找到是奇数的
            while(left < right && nums[right] % 2 == 0){
                right--;
            }
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
        return nums;
    }

}













